#include<stdio.h>
#include<stdlib.h>
struct node{
	int data;
	struct node *left;
	struct node *right;
	struct node *parent;
};
typedef struct node node;
node *head=NULL;
node *track(node*);
node *first(node*);
node* inorderSuccesor(node *ptr);

node* init(int i){

	node *temp=(node*)malloc(sizeof(node));
	temp->data=i;
	temp->left=NULL;
	temp->right=NULL;
	temp->parent=NULL;
	return temp;
}
int depth(node *temp){
	if(temp==NULL)
		return 0;
	else{
		int h1=depth(temp->left);
		int h2=depth(temp->right);
		int h3=h1>h2?h1+1:h2+1;
		return h3;
	}
		
}

void insert(int i){
	node *temp=init(i);
	if(head==NULL){
		head=temp;
	}
	else{
		node *ptr=head;
		while(ptr->left!=NULL&&ptr->right!=NULL){
			int h1=depth(ptr->left);
			int h2=depth(ptr->right);
			ptr=h1>h2?ptr->right:ptr->left;
		}
		temp->parent=ptr;

		if(ptr->left==NULL){
			ptr->left=temp;
		}
		else{
			ptr->right=temp;
		}
	}
}
void display(node *temp){
	if(temp==NULL)
		return;
	display(temp->left);
	printf("%d",temp->data);
	node *ptr=inorderSuccesor(temp);
	if(ptr!=NULL)
		printf("\n inorder succesor is %d\n",ptr->data);
	else
		printf("\n no succesor\n");
	display(temp->right);
}
node* inorderSuccesor(node *ptr){
	node *parent=ptr->parent;
			
	if(ptr->left==NULL && ptr->right==NULL){
		if(ptr==parent->left){
			return parent;
		}
		if(ptr==parent->right){
			return track(parent);
		}
		
	}
	else if(ptr->right!=NULL){
		return first(ptr->right);			
	}
	else if(ptr->right==NULL){
		node *parent2=ptr->parent;
		if(parent2->left==ptr){
			return parent2;
		}
		else{
			return track(parent2);
		}
	
	}
	
}	
node* track(node *ptr){
	node *parent=ptr->parent;
	while(parent!=NULL&&parent->left!=ptr){
		ptr=ptr->parent;
		parent=ptr->parent;
	}
	return parent;
}
node* first(node *ptr){
	while(ptr->left!=NULL){
		ptr=ptr->left;
	}
	return ptr;
}
void display1(node *temp){
	if(temp==NULL)return;
	display1(temp->left);
	printf("%d",temp->data);
	display1(temp->right);

}
int main(){
	insert(2);
	insert(4);
	insert(3);
	insert(5);
	insert(7);
	insert(9);
	insert(10);
	display1(head);
	printf("\n");
	display(head);
}
